#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<vector<string>> ans;
vector<string> res;
bool isValidated(int row, int col) {
    // 检查列冲突
    for (int i = 0; i < row; i++)
        if (res[i][col] == 'Q') return false;

    // 检查左斜角冲突
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        if (res[i][j] == 'Q') return false;

    // 检查右斜角冲突
    for (int i = row - 1, j = col + 1; i >= 0 && j < res.size(); i--, j++){
        if (res[i][j] == 'Q') return false;
    }
    return true;
}

void backtrack(int row) {
    if (row == res.size()) {
        ans.push_back(res);
        return;
    }

    for (int i = 0; i < res.size(); i++) {
        // check
        if (!isValidated(row, i)) {
            continue;
        }

        res[row][i] = 'Q';
        backtrack(row + 1);
        res[row][i] = '.';
    }

    return;
}

vector<vector<string>> solveNQueens(int n) {
    // 初始化
    string s(n, '.');
    for (int i = 0; i < n; i++) res.push_back(s);

    backtrack(0);
    return ans;
}

int main() {
    int n = 4;
    vector<vector<string>> ans = solveNQueens(4);
    return 0;
}